#include <bits/stdc++.h>
using namespace std;

// 【题目】力扣560. 和为 K 的子数组
// 【难度】中等
// 【提交】2025.10.09 https://leetcode.cn/problems/subarray-sum-equals-k/submissions/669075046/
// 【标签】哈希表；前缀和
class Solution_LC560 {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> mp;
        mp[0] = 1;
        int count = 0, pre = 0;
        for (auto& x : nums) {
            pre += x;
            if (mp.find(pre - k) != mp.end()) {
                count += mp[pre - k];
            }
            mp[pre]++;
        }
        return count;
    }
};

/**
 * @brief 学习总结：
 * 一、题意与模型
 * 给定一个整数数组nums和一个整数k，返回该数组中和为k的连续子数组的个数。
 * 模型：前缀和+哈希表，通过记录前缀和的出现次数来高效统计子数组数量。
 * 
 * 二、标准解法状态设计
 * 1. 使用变量pre记录当前前缀和（从0到当前位置的元素和）。
 * 2. 使用哈希表mp记录每个前缀和出现的次数。
 * 3. 对于每个位置，检查pre-k是否在哈希表中，如果在则累加对应次数。
 * 4. 更新当前前缀和的出现次数。
 * 
 * 三、你的实现思路
 * 使用前缀和技巧和哈希表，在一次遍历中统计所有满足条件的子数组数量。
 * 通过维护前缀和和其出现次数的映射，避免了暴力枚举所有子数组。
 * 
 * 四、逐行注释（带细节提醒）
 * unordered_map<int, int> mp; // 哈希表：前缀和 -> 出现次数
 * mp[0] = 1; // 初始状态：前缀和为0出现1次（空子数组）
 * int count = 0, pre = 0; // 初始化计数器和前缀和
 * 
 * for (auto& x : nums) { // 遍历数组
 *     pre += x; // 更新前缀和
 *     if (mp.find(pre - k) != mp.end()) { // 检查是否存在前缀和pre-k
 *         count += mp[pre - k]; // 累加满足条件的子数组数量
 *     }
 *     mp[pre]++; // 更新当前前缀和的出现次数
 * }
 * 
 * 五、正确性证明
 * 对于任意子数组nums[i..j]，其和可以表示为pre[j] - pre[i-1]。
 * 如果pre[j] - pre[i-1] = k，那么pre[i-1] = pre[j] - k。
 * 因此，对于每个位置j，我们只需要统计有多少个i满足pre[i] = pre[j] - k。
 * 哈希表mp记录的就是每个前缀和出现的次数。
 * 
 * 六、复杂度
 * 时间：O(n)，只需遍历数组一次，哈希表的查找和插入操作平均时间复杂度为O(1)。
 * 空间：O(n)，最坏情况下需要存储所有不同的前缀和。
 * 
 * 七、优缺点分析
 * 优点：
 *   - 时间复杂度低，只需一次遍历；
 *   - 代码简洁，实现高效；
 *   - 适用于包含负数的情况。
 * 缺点：
 *   - 需要额外的空间存储哈希表；
 *   - 对于极端情况（如大量哈希冲突），性能可能下降。
 * 
 * 八、改进建议
 * 1. 可以添加输入验证：if (nums.empty()) return 0;
 * 2. 使用reserve方法预分配哈希表空间以提高性能：
 *    mp.reserve(nums.size() + 1);
 * 3. 对于特殊场景（如k=0），可以添加特殊处理逻辑。
 * 
 * 九、一句话总结
 * 前缀和+哈希表是解决"和为K的子数组"问题的经典方法，你的实现准确且高效，
 * 能够熟练运用这一技巧解决相关问题。
 */